The present invention relates generally to hardware and software additions to an LDPC (Low Density Parity Check) decoder to implement a post-processing algorithm, and more particularly to additions which inject noise into the decoder to help it converge to a valid codeword and thereby lower the error floor.
Some Low Density Parity Check (LDPC) codes show an “error floor”, which is a reduction in the slope of the BER (Bit Error Rate) vs. channel SNR (signal-to-noise) curve, at low BER levels. This implies that the bit error rate at a given signal-to-noise ratio is higher than expected. This is undesirable for wireless backhaul customers. (The term “wireless backhaul” refers to communication links between cellular base-stations. It is a technology that is linked with carrying communication traffic among sites that are spaced in a circular manner, and is also used for two-way data transmission lines. More generally, error floor issues are a concern in any system requiring very low bit error rates.)
Post-processing is a technique that has been used to resolve a type of decoding errors called “trapping set errors”, which dominate in the error floor region. A trapping set error causes the decoder to be trapped in a local minimum with respect to a “cost function” that characterizes the quality of the decoder output. This implies the decoder did not find the global minimum of the cost function and was thus unable to converge to a valid codeword. Post-processing typically resolves trapping set errors by injecting noise into the LDPC decoder to break away from the local minimum (in this case, to find the global minimum point of a cost function which is also the global optimum point) and allow the decoder to converge.
In information theory, a low-density parity-check (LDPC) code is a linear error correcting code for a method of transmitting a message over a noisy transmission channel. An LDPC is constructed using a sparse bipartite graph (A bipartite graph is a graph whose vertices are divided into two independent sets. In a sparse bipartite graph there are relatively few edges or connections between the two sets.) LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close, or even arbitrarily close on the canonical binary erasures channel (BEC), to the theoretical maximum (the Shannon limit) for a symmetric memoryless channel. (The binary erasures channel is a common model of a communication channel.) The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative BP (belief propagation) techniques, LDPC codes (also known as Gallager codes) can be decoded in time linear to their block length. To form a codeword, the K input data bits are repeated and distributed to a set of constituent encoders. (A “frame” is equal to a codeword. Encoding means taking data bits and computing the corresponding parity bits. These are concatenated together to form the codeword.) The constituent encoders typically are accumulators, and each accumulator is used to generate a parity symbol. A single copy of the original data is transmitted with the parity bits (P) to make up the code symbols. The S bits from each constituent encoder are discarded. The foregoing encoding process is straightforward. The difficult problems lie in practical implementation of the decoding process. A brief description of the decoding process is given below.
The forward error-correction (FEC) requirements for “next-generation” wireless backhaul systems typically require a BER (Bit Error Rate) lower than 10−12 and a frame error rate lower than 10−10, a network throughput rate greater than 1 gigabytes per second, low power consumption, and low area in a silicon implementation. LDPC codes are becoming a very good candidate to meet the foregoing requirements, and have demonstrated a capability to provide performance very close to the Shannon limit when decoded with a low complexity iterative decoding algorithm. An LDPC code is defined by a sparse m×n parity check matrix H, where “n” represents the number of bits in the codeword and “m” represents the number of parity checks. A parity check matrix or H matrix contains “1”s and “0”s. Each row of the H matrix represents a parity constraint. For example, one row of the H matrix has n entries in total, with some entries being “1” and others being “0”. To define the parity constraint of this row, first note the positions of the “1” entries. Bits in the codeword in these positions must sum up to even parity. In this way, each row of the H matrix defines a different parity constraint involving a different set of bits in the codeword. The H matrix of an LDPC code can be illustrated graphically using a “bipartite graph” or “factor graph”, where each bit is represented by a variable processing node (VN) and each check is represented by a check node (CN). A variable node is also called a “bit node” or simply a “bit”, and these terms are used interchangeably. An “edge” exists between a variable node “i” and a check node “j” if and only if H(j,i)=1, where H(j,i)=1 means the element on the jth row and ith column of the parity check matrix H equals 1. Therefore, the positions of “1”s in the H matrix show the connections between VNs and CNs.
An LDPC code is decoded using a BP (belief propagation) algorithm that operates on the factor graph. In a BP (Belief Propagation) decoding, “soft messages” representing reliabilities are exchanged between variable nodes (VNs) and check nodes (CNs) to compute the likelihood of whether a bit is 1 or 0. (The “reliabilities” indicate the current belief that a given bit is 1 or 0.) The BP algorithm has two common implementations, including a precise “sum-product algorithm” and an approximate “min-sum algorithm”. The min-sum algorithm is simpler to implement and, with suitable modifications, provides excellent decoding performance.
As an example, a binary phase-shift keying (BPSK) modulation and an additive white Gaussian noise (AWGN) communication channel are assumed. The binary values 0 and 1 representing data bits are respectively mapped to 1 and −1 before transmission over the channel. The min-sum decoding can be explained using the factor graph. In the first step of decoding, each variable node xi is initialized with the subsequently described prior log-likelihood ratio (LLR) based on the received channel output yi. After initialization, variable nodes send the prior LLRs to the check nodes along the edges defined by the factor graph. The LLRs are re-computed based on parity constraints at each check node, and then are returned to the variable nodes. Each variable node then updates its decision based on a “posterior” LLR that is computed as the sum of the prior LLRs from the channel and the LLRs received from the check nodes. One round of message exchange between variable nodes and check nodes completes one iteration of decoding. To start the next iteration, each variable node passes the updated LLRs to the check nodes.
The LLRs passed between variable nodes and check nodes are known as “variable-to-check messages (L(qij))” and “check-to-variable messages (L(rij))”, where “i” is the variable node index and “j” is the check node index. In representing the connectivity of the factor graph, Col[i] refers to the set of all the check nodes “connected” to the “i”th variable node and Row[j] refers to the set of all the variable nodes “connected to” the “j”th check node. (The term “connected” refers to the variable nodes and check nodes that exchange messages with each other, i.e., communicate with each other.) A “hard decision” can optionally be made in each iteration based on the above mentioned posterior LLR. (A hard decision can be checked after each iteration, or some iterations can be run first and then checked once afterward.) The iterative decoding is allowed to run until the hard decisions satisfy all of the parity check equations or when an upper limit on the number of iterations is reached.
It is well-known that LDPC decoders suffer from the previously mentioned error floor problems. The post-processing approach and hardware are designed to improve the error floor. Over the past decade, it has been found that the excellent performance of LDPC is only observed up to a moderate bit error rate (BER), leading to the previously mentioned “error floor”. The error floor phenomenon can be characterized as an abrupt slope decrease of a code's performance curve past a certain moderate BER level. Solving the error floor problem has been a critical issue for both coding theorists and practitioners, since more and more systems, such as data storage devices and high-speed communications systems, require extremely low error rates.
Solving the error floor problem has been an important focus of research in coding theory and practical decoder designs. Past experiments have shown that error floors can be caused by various practical decoder implementations. Improved algorithm implementation and better numerical quantization can suppress these effects. However, error floors are fundamentally attributed to non-codeword “trapping sets” associated with LDPC codes. A trapping set refers to a set of bits in a codeword which, when received incorrectly, causes the belief propagation (BP) decoding algorithm to be trapped in the above mentioned “local minimum”. A trapping can be thought of as a “special combinatorial structure” involving cycles in the LDPC bipartite graph that reinforces incorrect bits during BP decoding.
Much work has been done on lowering the error floor by improving code constructions using methods such as progressive edge growth (PEG), cycle avoidance, code doping, and cyclic lifting. Although these methods are effective, the resulting code structures often complicate the decoder hardware design. An alternative way is to improve the BP decoding algorithm by methods such as scaling, offsetting, or trial and error, but these methods are mostly based on heuristics and their effectiveness is limited. Some of these methods even require extra steps that are incompatible with BP decoding, leading to a higher complexity and much longer latency (the time it takes for the decoder to produce the decoded codeword). A theoretically more effective approach is to target the combinatorial structures of absorbing sets to modify the decoding algorithm, an example of which is the bi-mode syndrome erasure decoding algorithm, although it sometimes falls short when the erasure decoding runs into its own local minima. For example, See “An Efficient 10 GBASE-T Ethernet LDPC Decoder Design with Low Error Floors” by Zhengya Zhang, et. al, IEEE Journal of Solid-State circuits, Volume 45, No. 4, April, 2010, especially FIG. 7 which shows hard decision outputs used to determine whether a message should be biased before check node processing. Also see “Lowering LDPC Error Floors by Postprocessing” by Zhengya Zhang, et al., for publication in the IEEE “GLOBECOM” 2008 proceedings.
The above-mentioned prior art in post-processing hardware only injects noise once (single-shot noise injection) in the decoding process. Furthermore, the prior art in post-processing hardware only allows changing magnitude of the noise. In the error floor region, the prior art LDPC decoders cannot successfully decode certain received codewords. Prior art post-processing helps the decoder decode some of these failures, but the real goal is to be able to decode all of the failures, and unfortunately, the techniques of the prior art can only resolve a limited type and number of errors. This consequently directly limits the amount of error floor improvement that as a practical matter is achievable by the prior art.
Thus, there is an unmet need for a better way of solving the error floor problems that have been critical issues in designing data storage devices and high-speed communications systems which require extremely low error rates.
There also is an unmet need for a post-processing system and method that can resolve more types of decoding errors than the prior art, thus improving the bit error rate in the error floor region.
There also is an unmet need for a post-processing system and method for implementing the described post-processing technique that are compatible with existing high throughput decoder architectures.
There also is an unmet need for improved post-processing capable of better improving the error floor for LDPC decoding for a substantially higher bit error rate (BER) then has been achievable by prior art post-processing.